#include <vector>

using std::vector;

class Solution {
public:
    int jump(vector<int>& nums) {
        int end = 0;
        int far = 0;
        int ret = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            far = std::max(far, i + nums[i]);
            if (i == end) {
                end = far;
                ret++;
            }
        }
        return ret;
    }
};